# 24/100 链表-回文链表
# leetcode第234题: https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/16
from typing import Optional
from leetcode import test
from leetcode.bds import ListNode
from leetcode.bds import ListConvert


def isPalindrome(head: Optional[ListNode]) -> bool:
    """一个简单的方法, 遍历链表添加到一个数组中
    空间复杂度O(n) 时间复杂度O(n)
    """
    curr = head
    l = list([head.val])
    while curr.next:
        curr = curr.next
        l.append(curr.val)

    n = len(l)
    for i in range(n // 2):
        if l[i] != l[n - 1 - i]:
            return False

    return True


def isPalindrome_rec(head: Optional[ListNode]) -> bool:
    """利用递归的方法, 递归的本质是一个栈, 拥有LIFO的特点
    空间复杂度O(n) 时间复杂度O(n)"""
    left = head

    def recursively_check(right=head):  # [1, 2, 2, 1]
        nonlocal left
        if right is not None:
            if not recursively_check(right.next):
                return False
            if left.val != right.val:
                return False
            left = left.next
        return True

    return recursively_check()


def isPalindrome_dbpnt(head: Optional[ListNode]) -> bool:
    """使用快慢指针的方式, 将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。
    注意: 使用后应该还原链表
    空间复杂度O(1) 时间复杂度O(n)"""
    if head is None:
        return True

    def mid_node(head):
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(head):
        """翻转链表"""
        cur, pre = head, None
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
        return pre  # !!注意最后反转后的头节点是pre，此时cur为空

    first_half_end = mid_node(head)  # 链表中间的节点
    second_half_start = reverse_list(first_half_end.next)  # 后半部分

    while second_half_start:
        if head.val != second_half_start.val:
            return False
        head = head.next
        second_half_start = second_half_start.next

    # 还原链表
    first_half_end.next = reverse_list(second_half_start)
    return True


if __name__ == '__main__':
    head1 = ListConvert.list_to_link([1, 2, 2, 1])
    head2 = ListConvert.list_to_link([1, 2])
    head3 = ListConvert.list_to_link([1, 2, 3, 4, 3, 2, 1])
    inp = [{"head": head1}, {"head": head2}, {"head": head3}, ]
    out = [True, False, True]

    test.test_function(isPalindrome, inp, out, times=10000)
    test.test_function(isPalindrome_rec, inp, out, times=10000)
    test.test_function(isPalindrome_dbpnt, inp, out, times=10000)
